iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 30
1
自我挑戰組

神羅天征! 一起(爆肝)征服程式解題系列 第 30

[Day 30] LeetCode - 125 Valid Palindrome

  • 分享至 

  • xImage
  •  

本篇同步發布於Blog:[解題] LeetCode - 125 Valid Palindrome

平台:

LeetCode

題號:

125 - Valid Palindrome

題目連結:

https://leetcode.com/problems/valid-palindrome/

題目說明:

        給1個字串s,求s是否為s的palindrome(回文),這題的Palindrome的定義是字串的英文字母和數字是左右對稱,且英文大小寫不分,如果是其他字元則略過不比對。

比如範例輸入s = "A man, a plan, a canal: Panama",它扣掉空白、逗號、分號,全轉成小寫的話,會是"amanaplanacanalpanama",會是左右對稱的回文。

特殊案例是 s = ",!",全都只有標點符號,這也是回文。

解題方法:

     建立2個索引值i和j,分別從字串s的左邊和右邊掃描,找到第1個英文字母或數字則停下,確認是否符合回文定義的比對規則,如果不相同,則並不是回文。當i >= j,代表已經都比對完,則屬於回文。

而判斷是否相同字母或數字,可以用字元的ASCII範圍檢查,並回傳自定義的索引值,比如'A'和'a'回傳0、'0'回傳26(與前面英文字母不同)。

難度為Easy

程式碼 (C++ 與 C#):

#include <iostream>
using namespace std;

class Solution {
private: 
    int getAlphanumericCommonIndex(char c){
        int index;
        if(c >= 'a' && c <= 'z'){
            index = c - 'a';
        }
        else if(c >= 'A' && c <= 'Z'){
            index = c - 'A';
        }
        else{
            index = c - '0' + 26;
        }
        
        return index;
    }
public:
    bool isPalindrome(string s) {
        int n = s.length();
        int i = 0, j = n-1;
        bool isOk = true;
        int left, right;
        while(i < j){
            while(i < n && !(s[i] >= '0' && s[i] <= '9') && !(s[i] >= 'a' && s[i] <= 'z') && !(s[i] >= 'A' && s[i] <= 'Z')){
                ++i;
            }
            
            while(j >= 0 && !(s[j] >= '0' && s[j] <= '9') && !(s[j] >= 'a' && s[j] <= 'z') && !(s[j] >= 'A' && s[j] <= 'Z')){
                --j;
            }

            if(i >= j){
                break;
            }
            
            left = getAlphanumericCommonIndex(s[i]);
            right = getAlphanumericCommonIndex(s[j]);

            
            if(left != right){
                isOk = false;
                break;
            }
            
            ++i;
            --j;
        }
        
        return isOk;
    }
};

int main() {
	Solution sol;
	cout << sol.isPalindrome("A man, a plan, a canal: Panama") << endl;
	cout << sol.isPalindrome("race a car") << endl;
	return 0;
}
using System;

namespace LeetCode125
{
	public class Solution {
	    private int GetAlphanumericCommonIndex(char c){
	        int index;
	        if(c >= 'a' && c <= 'z'){
	            index = c - 'a';
	        }
	        else if(c >= 'A' && c <= 'Z'){
	            index = c - 'A';
	        }
	        else{
	            index = c - '0' + 26;
	        }
	        
	        return index;
	    }
	    
	    public bool IsPalindrome(string s) {
	        int n = s.Length;
	        int i = 0, j = n-1;
	        bool isOk = true;
	        int left, right;
	        while(i < j){
	            while(i < n && !(s[i] >= '0' && s[i] <= '9') && !(s[i] >= 'a' && s[i] <= 'z') && !(s[i] >= 'A' && s[i] <= 'Z')){
	                ++i;
	            }
	            
	            while(j >= 0 && !(s[j] >= '0' && s[j] <= '9') && !(s[j] >= 'a' && s[j] <= 'z') && !(s[j] >= 'A' && s[j] <= 'Z')){
	                --j;
	            }
	
	            if(i >= j){
	                break;
	            }
	            
	            left = GetAlphanumericCommonIndex(s[i]);
	            right = GetAlphanumericCommonIndex(s[j]);
	
	            
	            if(left != right){
	                isOk = false;
	                break;
	            }
	            
	            ++i;
	            --j;
	        }
	        
	        return isOk;
	    }
	}
	
	public class Program
	{
		public static void Main()
		{
			Solution sol = new Solution();
			Console.WriteLine(sol.IsPalindrome("A man, a plan, a canal: Panama"));
			Console.WriteLine(sol.IsPalindrome("race a car"));
			Console.Read();
		}
	}
}

GITHUB位置(C++ 與 C#):

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/100-199/125.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/100-199/125.cs


上一篇
[Day 29] LeetCode - 242 Valid Anagram
系列文
神羅天征! 一起(爆肝)征服程式解題30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言